package m202403.d13;

import java.util.HashMap;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/3/13 14:10
 */
//740. 删除并获得点数
public class Q740 {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer r = map.getOrDefault(num, 0);
            map.put(num, r + num);
        }
        int[] array = map.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();
        return doDP(map, array);
    }

    public int doDP(Map<Integer, Integer> map, int[] nums) {
        if (nums.length == 1) {
            return map.get(nums[0]);
        }

        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = map.get(nums[0]);
        for (int i = 2; i <= nums.length; i++) {
            if (nums[i - 2] + 1 < nums[i - 1]) {
                dp[i] = dp[i - 1] + map.get(nums[i - 1]);
            } else {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + map.get(nums[i - 1]));
            }
        }
        return dp[nums.length];
    }
}
